package com.lun.swordtowardoffer2.c01;

public class Divide {
	
	public int divide(int dividend, int divisor) {
		//(-2^{31})/(-1)=2^{31}这数在Java int会溢出
		if (dividend == Integer.MIN_VALUE && divisor == -1)
			return Integer.MAX_VALUE;
		int negative = (dividend >>> 31) ^ (divisor >>> 31); 
		//不管正负都转换成负数处理（不能都转换成正数的原因是，
		//-2^{31}（Integer.MIN_VALUE）转正操作还是-2^{31}（Integer.MIN_VALUE））
		dividend = -Math.abs(dividend);
		divisor = -Math.abs(divisor);
		int result = divideCore(dividend, divisor);
		return negative == 1 ? -result : result;
	}

	private int divideCore(int dividend, int divisor) {
		int result = 0;
		while (dividend <= divisor) {//此时被除数与除数都被先前步骤弄为负数
			int value = divisor;
			int quotient = 1;
			//Integer.MIN_VALUE >> 1 为下界，若某值越界，翻倍后会溢出
			while (value >= (Integer.MIN_VALUE >> 1) && dividend <= (value << 1)) {//注意处理负数时的违和感
				quotient += quotient;
				value += value;
			}
			result += quotient;
			dividend -= value;
		}
		return result;
	}

}
